package java学习.代码随想录.动态规划;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/10 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 最大子序和 {
    /**
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *             0  1 2  3 4  5 6  7 8
     * 示例: 输入: [-2,1,-3, 4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     *             -2 1  -2 4  3 5 6 1 5
     * 定义： dp[i] = 包含 nums[i] 的最大连续子序和
     * dp[i] = dp[i-1]+nums[i],nums[i]
     * dp[0] = nums[0] 因为至少包含一个元素
     *
     */

    public static int maxSubArray(int[] nums) {
        if (nums.length==0){
            return 0;
        }

        int [] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
//            max = Math.max(max,dp[i]);
            max = Math.max(max, dp[i]);
        }
        // System.out.println(Arrays.toString(dp));
        return max;
    }
    public int maxSubArray1(int[] nums) {
        int pre = 0;
        int res = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            res = Math.max(res, pre);
        }
        return res;
    }
    public static void main(String[] args) {
//        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int[] nums = {1};

        System.out.println("maxSubArray(nums) = " + maxSubArray(nums));
    }
}
